package problem.year2023.month05

import problem.year2023.month05.Day04.maxTotalFruits
import kotlin.math.abs

/**
 * @author LiangMu
 * @version \$Id: Day04.java, v 0.1, 2023年05月04日 10:35 LiangMu Exp $$
 */
object Day04 {
    /**
     * 在一个无限的 x 坐标轴上，有许多水果分布在其中某些位置。给你一个二维整数数组 fruits ，
     * 其中 fruits[i] = [positioni, amounti] 表示共有 amounti 个水果放置在 positioni 上。
     * fruits 已经按 positioni 升序排列 ，每个 positioni 互不相同 。
     *
     * 另给你两个整数 startPos 和 k 。最初，你位于 startPos 。从任何位置，你可以选择 向左或者向右 走。
     * 在 x 轴上每移动 一个单位 ，就记作 一步 。
     * 你总共可以走 最多 k 步。你每达到一个位置，都会摘掉全部的水果，水果也将从该位置消失（不会再生）。
     *
     * 返回你可以摘到水果的 最大总数 。
     *
     * 示例1：
     * 输入：fruits = [[2,8],[6,3],[8,6]], startPos = 5, k = 4
     * 输出：9
     * 解释：
     * 最佳路线为：
     * - 向右移动到位置 6 ，摘到 3 个水果
     * - 向右移动到位置 8 ，摘到 6 个水果
     * 移动 3 步，共摘到 3 + 6 = 9 个水果
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode.cn/problems/maximum-fruits-harvested-after-at-most-k-steps
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     */
    fun maxTotalFruits(fruits: Array<IntArray>, startPos: Int, k: Int): Int {
        var left = 0
        var right = 0
        var sum = 0
        var ans = 0
        val n = fruits.size
        // 每次固定住窗口右边界
        while (right < n) {
            sum += fruits[right][1];
            // 移动左边界
            while (left <= right && step(fruits, startPos, left, right) > k) {
                sum -= fruits[left][1];
                left++;
            }
            ans = ans.coerceAtLeast(sum);
            right++
        }
        return ans;
    }

    private fun step(fruits: Array<IntArray>, startPos: Int, left: Int, right: Int): Int {
        return abs(startPos - fruits[right][0]).coerceAtMost(
            abs(startPos - fruits[left][0])
        ) + fruits[right][0] - fruits[left][0]
    }
}


fun main() {
    val arr = arrayOf(
        intArrayOf(0, 9),
        intArrayOf(4, 1),
        intArrayOf(5, 7),
        intArrayOf(6, 2),
        intArrayOf(7, 4),
        intArrayOf(10, 9)
    )
    println(maxTotalFruits(arr, 5, 4))
}
